Supplementary Material for “SMETANA: Accurate and Scalable Algorithm for Probabilistic Alignment of Large-Scale Biological Networks”

To measure the global correspondence score between any two nodes ui ∈ G1 and vj ∈ G2, we compute the the long-run proportion of time that the random walker stays at the node pair x = (ui, vj) in GX. We model the semi-Markov random walk on GX such that µ(x), the expected amount of time that the random walker spends at a node pair x = (ui, vj), is proportional to the node similarity h(ui, vj). As a result, both higher interaction similarity as well as higher node similarity between nodes would lead to higher global similarity between them. Thus, as discussed shown in [1, 2], this global correspondence score can be computed as follows: s(ui, vj) = piX (x)µ(x)∑ x′∈VX piX (x ′)µ(x′) pi1(ui)pi2(vj)h(ui, vj)∑|U| i′=1 ∑|V| j′=1 pi1(ui′)pi2(vj′)h(ui ′ , vj′